package 剑指offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class p34二叉树中和为某一值的路径 {
    private List<List<Integer>> res;
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        res=new LinkedList<>();
        LinkedList<Integer> list=new LinkedList<>();//记录此时寻找过程中的节点值，不符合要求和判断过的节点要进行删除
        findSum(root,target,0,list);

        return res;
    }

    private void findSum(TreeNode node, int target, int sum, LinkedList<Integer> list) {
        if (node!=null) {
            list.add(node.val);
            sum += node.val;
            if (node.left==null && node.right==null) {
                //遍历到 叶子节点
                if (sum==target) {
                    List<Integer> path=new LinkedList<>(list);
                    res.add(path);//把当前找到的的路径存入 二维数组中
                }
            }else {
                //继续遍历，直到 叶子节点，才能判断是否符合要求
                findSum(node.left,target,sum,list);
                findSum(node.right,target,sum,list);
            }
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> list=new LinkedList<>();
        for (int i = 0; i <3; i++) {
            list.add(i);
            if (i==2) {
                System.out.println(list);
            }
        }

        list.remove(list.size()-1);
        System.out.println(list);
    }
}
